// 非递归版 自顶向底
#include <stdio.h>
#include <stdlib.h>

// 把两个有序数组al[]和ah[]进行合并
// a[low]~a[mid] -- al[]
// a[mid+1]~a[high] -- ah[]
void merge(int a[], int low, int mid, int high)
{
    if (low < high)
    {
        int *b = (int *)malloc(sizeof(int) * (high - low + 1));
        int i, j;
        i = low, j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high)
        {
            if (a[i] < a[j])
                b[k++] = a[i++];
            else if (a[i] >= a[j])
                b[k++] = a[j++];
        }

        while (i <= mid)
        {
            b[k++] = a[i++];
        }
        while (j <= high)
        {
            b[k++] = a[j++];
        }
        for (int m = 0; m < k; m++)
        {
            a[low + m] = b[m];
        }
        free(b);
    }
}

void merge_sort(int a[], int n)
{
    // 注意d和i的取值范围
    // d < n*2  d 的含义是 每次low--high的长度
    // 1. n很凑巧 log n 为整数 d==n 的时候是最后一次归并
    // 2. n不凑巧 log n 不为整数 d永远不会等于n n<d<2*n 的时候 是最后一次归并
    // i<n
    for (int d = 2; d < n * 2; d *= 2)
    {
        for (int i = 0; i < n; i += d)
        {
            int mid, high;
            high = i + d - 1;
            mid = (i + high) / 2;
            // high 超出 n的范围时 high和mid都应该重新取值
            // 此时分为两段 i~mid mid~n-1
            // 所以mid 并不是(i+n-1)/2 而是 i+d/2-1
            if (high > n - 1)
            {
                high = n - 1;
                mid = i + d / 2 - 1;
            }
            merge(a, i, mid, high);
        }
        for (int i = 0; i < n; i++)
            printf("%3d", a[i]);
        printf("\n");
    }
}

int main()
{
    /*******************code*******************/
    int a[] = {4, 3, 8, 2, 7, 11, 6, 1, 9, 0, 65, 32, 10, 15, 36, 12, 13};
    int n = 17;
    merge_sort(a, n);
    printf("merge_sort\n");
    for (int i = 0; i < n; i++)
        printf("%3d", a[i]);
    printf("\n");
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
